The output of a DFS is more than just a visit order; it's a structural decomposition of the graph into a DFS Tree and a set of non-tree edges.
- The path DFS takes to discover new nodes forms a subgraph called a DFS Tree (or a forest for disconnected graphs).
- This tree reveals the graph's deep structure and the parent-child relationships created by the recursive calls.
- The true power of DFS comes from classifying the graph's remaining edges relative to this tree.
- By analyzing these non-tree edges, we can uncover key properties like cycles, connectivity, and topological orderings.
| Edge Type | What it Reveals |
|---|---|
| Tree Edge | Forms the backbone of the traversal. |
| Back Edge | Points to an ancestor. Crucial for detecting cycles. |
| Forward/Cross Edge | Points to descendants or other branches. |